In order to find out an external environment of a mobile machine or the like, such as a robot, an automobile, a ship, an aircraft or the like, from its inside or outside, it is important to recognize surrounding objects and their shapes. In particular, when the mobile machine is allowed to automatically travel, shape recognition is more important in terms of avoidance of danger or the like. Moreover, there is a large social demand for human shape estimation, which is applicable to security services or care services. As means for estimating a shape of an object, an imaging system employing radar has attracted attention. For example, a UWB radar, which utilizes an ultra-wide band (UWB) signal, can measure a shape of a near-field target at a high resolution, and therefore, has been used in many applications for ground probing and nondestructive testing. However, in conventional ground penetrating radar imaging, most estimation algorithms for estimating a shape from a measurement result are based on iterative improvement, iterative calculation or the like, and therefore, it takes a long time to complete shape estimation. Therefore, it is difficult to directly apply the conventional techniques to a real-time process required for the aforementioned robots and the like.
Therefore, the present inventors have developed and proposed a high-speed shape estimation algorithm which enables a real-time process, called SEABED (Shape Estimation Algorithm based on BST (Boundary Scattering Transform) and Extraction of Directly scattered waves). In SEABED, a shape of an object is estimated by utilizing a reversible conversion relationship established between a relationship between a time delay of a scattered wave of a transmission signal which is obtained by changing a transmission/reception location, and the transmission/reception location, and the shape of the object (e.g., Patent Document 1 and Non-Patent Documents 1 to 5).
The principle of the SEABED method will be described below. FIG. 15 is a diagram for describing how antenna scanning is performed in the SEABED method. In the SEABED method, it is assumed that an object to be measured (target object) is a physical object which has a clear boundary, and the boundary is measured to obtain a “quasi-wavefront.” A shape of the target object is obtained by inverse-transforming the quasi-wavefront.
In the description of the principle, referring to FIG. 15, a two-dimensional problem is dealt with, assuming that a target object O and a transmission/receiving antenna A are provided in the same plane. It is also assumed that radio waves propagate as Transverse Electric (TE) waves. Space in which the target object O and the transmission/receiving antenna A are located is referred to as “r-space (r-domain),” and if a set is expressed in r-domain, the set is referred to as an “expression in r-domain.” Also, a point in r-domain is expressed as (x, y). Here, both x and y (y>0) are normalized using the center wavelength λ of a transmitted pulse in vacuum. The transmission/receiving antenna A is assumed to be omnidirectional, and repeatedly transmit and receive monocycle pulses at measurement locations xn (n=1 to N (integers)) spaced at predetermined intervals (e.g., regular intervals) while scanning on the x-axis in r-domain. In addition, a reception electric field at a measurement location (x, y)=(X, 0) of the transmission/receiving antenna A is defined as s′(X, Y), and Y is defined as Y=(c×t)/(2×λ), where t is a period of time from transmission to reception, and c is the speed of light in vacuum. Note that y>0 and therefore Y>0, and also, a time at which an instantaneous envelope at a measurement location xn of the transmission/receiving antenna A becomes maximum is assumed to be t=−0.
Moreover, for the purpose of removal of noise, a matched filter using a transmission waveform is applied to s′(X, Y) in the Y-direction, and a received waveform obtained by the application of the matched filter is newly set as s(X, Y). This s(X, Y) is used as data for obtaining a shape of the target object O. Here, space expressed as (X, Y) is referred to as “d-space (d-domain),” and if a set is expressed in d-space, the set is referred to as an “expression in d-domain.” X and Y are normalized using the center wavelength and the center frequency of a transmitted pulse, respectively.
Changes in the complex permittivity ε(x, y) of the target object O having a continuous boundary surface are assumed to be a set of a plurality of piecewise differentiable curves. Specifically, the complex permittivity s(x, y) of the target object O is expressed as:
                                                                    ∇                              ɛ                ⁡                                  (                                      x                    ,                    y                                    )                                                                          2                =                              ∑                          q              ∈              H                                ⁢                                    a              q                        ⁢                          δ              ⁡                              (                                  y                  -                                                            g                      q                                        ⁡                                          (                      x                      )                                                                      )                                                                        (                  Expression          ⁢                                          ⁢          1                )            
Here, it is assumed that gq(x) is a differentiable single-valued function, and q={(x, y)|y=gq(x), xεJq}εH, where Jq is the domain of definition of the function gq(x), aq is a positive constant depending on qεH, and H is the set of all q′s. Elements of H are “target boundary surfaces.”
A subset P of d-space is defined as:P={(X,Y)|∂s(X,Y)/∂Y=0}  (Expression 2)
With respect to a connected closed set p⊂P, a domain Ip is defined as:Ip=[min(X,Y)εpX,max(X,Y)εpX]  (Expression 3)
A single-valued function fp(X) is present which has the domain of definition Ip with respect to p if there is only one Y satisfying (X, Y)εp with respect to an arbitrary XεIp, and satisfies Y=fp(X). A set of p′s for which the function fp(X) is differentiable and |∂fp(X)/∂X|≦1 is defined as G, and elements of G are referred to “quasi-wavefronts.”
When Expression (1) is satisfied, direct scattered waves from a boundary hold information about a target boundary surface (expressing a surface and a shape of the target object O). This is similarly established in a known medium having a constant propagation speed, although it is hereinafter assumed for the sake of simplicity that all propagation paths of direct waves are in vacuum.
FIGS. 16(a) and 16(b) are diagrams for describing a boundary scattering transform. FIG. 16(a) shows an example of a change in complex permittivity in r-domain, and FIG. 16(b) shows a quasi-wavefront of d-domain corresponding to r-domain of FIG. 16(a).
If it is assumed that p corresponds to direct scattering from q, it can be seen form FIG. 16(a) that a point (X, Y) on p is expressed as Expression (4) using a relationship between the length of a vertical line from the transmission/receiving antenna A to a curve Lq expressed by q, and a location of the transmission/receiving antenna A. A transform expressed as Expression (4) is referred to as a boundary scattering transform.
Only a time delay of a scattered wave, i.e., Y is observed at the location of the antenna A of FIG. 16(a), and a scattering point is located somewhere on a circle whose center is A and whose radius is Y, however, an angle from which the scattered wave comes is unknown. Y corresponds to a time delay of a scattered wave with respect to each antenna location X. FIG. 16(b) shows a relationship between X and Y.
Note that a curve expressed by p may have a plurality of Y values with respect to some X value. Symbols ◯ and Δ shown in FIG. 16(b) are an example of such a case. These symbols ◯ and Δ correspond to symbols ◯ and Δ shown in FIG. 16(a), respectively. The lengths of a solid line and a dashed line of FIG. 16(a) are the same as those of FIG. 16(b), respectively. The solid line and the dashed line at an antenna location P of FIG. 16(a) are both perpendicular to Lq. Points indicated by symbols ◯ and Δ are scattering points of radio waves, which are received as scattered waves having different time delays in FIG. 16(b).
                    {                                                            X                =                                  x                  +                                      y                    ⁢                                                                  ⅆ                        y                                                                    ⅆ                        x                                                                                                                                                                    Y                =                                  y                  ⁢                                                            1                      +                                                                        (                                                                                    ⅆ                              y                                                                                      ⅆ                              x                                                                                )                                                2                                                                                                                                                    (                  Expression          ⁢                                          ⁢          4                )            
Note that (x, y) is a point located on q.
By calculating an inverse transform of this boundary scattering transform, a shape of the target object O can be obtained from a received waveform. This inverse transform is obtained as expressed as Expression (5). This inverse transform is referred to as an inverse boundary scattering transform.
                    {                                                            x                =                                  X                  -                                      Y                    ⁢                                                                  ⅆ                        Y                                                                    ⅆ                        X                                                                                                                                                                    y                =                                  Y                  ⁢                                                            1                      -                                                                        (                                                                                    ⅆ                              Y                                                                                      ⅆ                              X                                                                                )                                                2                                                                                                                                                    (                  Expression          ⁢                                          ⁢          5                )            
Although two-dimensional measurement has been described above, the SEABED method can be easily extended to three-dimensional measurement. Also, although it has been assumed above that the transmission/receiving antenna A travels along a straight line, a transform expression corresponding to a case where the transmission/receiving antenna A travels along any curves can be easily obtained.
For example, a boundary scattering transform for a three-dimensional problem is expressed as Expression (6), and its inverse transform is expressed as Expression (7).
                    {                                                            X                =                                  x                  +                                      z                    ⁢                                                                  ∂                        z                                                                    ∂                        x                                                                                                                                                                    Y                =                                  y                  +                                      z                    ⁢                                                                  ∂                        z                                                                    ∂                        y                                                                                                                                                                    Z                =                                  z                  ⁢                                                            1                      +                                                                        (                                                                                    ∂                              z                                                                                      ∂                              x                                                                                )                                                2                                            +                                                                        (                                                                                    ∂                              z                                                                                      ∂                              y                                                                                )                                                2                                                                                                                                                    (                  Expression          ⁢                                          ⁢          6                )                                {                                                            x                =                                  X                  -                                      Z                    ⁢                                                                  ∂                        Z                                                                    ∂                        X                                                                                                                                                                    y                =                                  Y                  -                                      Z                    ⁢                                                                  ∂                        Z                                                                    ∂                        Y                                                                                                                                                                    z                =                                  Z                  ⁢                                                            1                      -                                                                        (                                                                                    ∂                              Z                                                                                      ∂                              X                                                                                )                                                2                                            -                                                                        (                                                                                    ∂                              Z                                                                                      ∂                              Y                                                                                )                                                2                                                                                                                                                    (                  Expression          ⁢                                          ⁢          7                )            
In the SEABED method which estimates a shape of the target object O from a received waveform using Expression (5) (Expression (7) for a three-dimensional problem), the shape of the target object O is specifically measured by executing the following process.
FIG. 17 is a flowchart showing a procedure when a shape of an object is measured by the SEABED method.
As shown in FIG. 17, in the conventional SEABED method, at each measurement location xn a shape measurement instrument (not shown) transmits a monocycle pulse (transmitted pulse), receives a reflected wave of the transmitted pulse reflected from the target object O, performs analog-to-digital conversion (hereinafter abbreviated as “A/D conversion”) with respect to the received wave, and stores the resultant wave, while scanning the omnidirectional transmission/receiving antenna A as shown in FIG. 15 (step S101).
Specifically, at a the measurement start location x1, the shape measurement instrument initially transmits a monocycle pulse (transmitted pulse) from the omnidirectional transmission/receiving antenna A, receives a reflected wave of the transmitted pulse reflected from the target object O, performs A/D conversion with respect to the received wave to generate a first received signal, and stores the first received signal. After completing transmission and reception at the measurement start location x1, at a measurement location x2 which is at a predetermined interval away from the measurement start location x1 the shape measurement instrument transmits a monocycle pulse (transmitted pulse) from the transmission/receiving antenna A, receives a reflected wave of the transmitted pulse reflected from the target object O, performs A/D conversion with respect to the received wave to generate a second received signal, and stores the second received signal. Thereafter, similarly, at each measurement location xn (from the measurement start location x1 to a measurement end location xN), the shape measurement instrument transmits a monocycle pulse (transmitted pulse) from the transmission/receiving antenna A, receives a reflected wave of the transmitted pulse reflected from the target object O, performs A/D conversion with respect to the received wave, and stores the resultant received signal. Thus, the first received signal at the measurement start location x1 to an N-th received signal at the measurement end location xN are obtained.
Next, in step S102, the shape measurement instrument obtains a cross-correlation between a waveform of each of the first to N-th received signals and a waveform of a reference signal, thereby obtaining first to N-th correlation waveforms corresponding to the first to N-th received signals, respectively. A correlation function ρ(τ) is expressed as:ρ(τ)=∫s(t)·r(t+τ)dt  (Expression 8)where τ is the time delay, r(t) is the reference signal, and s(t) is the received signal. Note that the integration range is a range within which the received signal s(t) exists.
Here, the waveform of the reference signal is the waveform of the transmitted pulse, which is based on the assumption that the waveform of the received signal has the same shape as that of the transmitted pulse. A process in this step corresponds to application of a matched filter to the received signal.
Next, in step S103, the shape measurement instrument obtains extremums (relative maximums and relative minimums) in the first to N-th correlation waveforms.
Next, in step S104, the shape measurement instrument connects adjacent extremums. More specifically, the shape measurement instrument connects extremums in a manner which satisfies Expression (9):−1≦(location of extremum Mn−location of extremum Mn-1)/(measurement location Xn−measurement location Xn-1)≦1  (Expression 9)
Here, the location of extremum Mn is a location in an XY plane of an extremum obtained from an n-th correlation waveform obtained at the measurement location xn. A curve obtained by connecting the extremums in this manner is a quasi-wavefront.
Next, in step S105, the shape measurement instrument extracts a true quasi-wavefront. The quasi-wavefront obtained by the process of step S104 includes undesired quasi-wavefronts, such as one which is generated due to noise, one which is generating by extracting a vibration component, one which is generated due to multiple scattering, and the like. Therefore, it is necessary to remove these undesired quasi-wavefronts so as to extract a true quasi-wavefront which truly indicates a boundary surface of the object O. In this process of extracting a true quasi-wavefront, an evaluation value wp which is defined as Expression (10) is firstly used to select and extract a quasi-wavefront having an evaluation value wp which is larger than a predetermined threshold α. If the threshold α is excessively small, a large number of undesired quasi-wavefronts are included. If the threshold a is excessively large, true quasi-wavefronts are also removed. Therefore, the threshold α is experimentally or empirically set in view of the maximum value of the evaluation value wp.wp=|∫xεIps(X,fp(X))dX|2  (Expression 10)
The evaluation value wp takes a large value when a received signal on a quasi-wavefront has a large amplitude, and the domain of definition of fp(X) is wide.
Here, if only Expression (10) is used to extract true quasi-wavefronts, then when a quasi-wavefront caused by, for example, noise is located close to a true quasi-wavefront, the evaluation value wp may be large and therefore the quasi-wavefront may not be removed. Therefore, when (x, y)εp1 and (x, y)εp2 are established where p1, p2εG, p1≠p2 and wp1≦wp2, quasi-wavefronts are divided, i.e., p1→p1′, p1″ (note that p1′∪p1″=p1 and p1′∩p1″=p1∩p2) to obtain the evaluation value wp, thereby removing undesired quasi-wavefronts.
Thereafter, in the true quasi-wavefront extraction process, Fp (known as a first Fresnel zone) expressed as Expression (11) and a new evaluation value Wp defined as Expression (12) are secondly used to select and extract a quasi-wavefront having an evaluation value Wp larger than a predetermined threshold β. If the threshold β is excessively small, a large number of undesired quasi-wavefronts are included. If the threshold β is excessively large, true quasi-wavefronts are also removed. Therefore, the threshold β is experimentally or empirically set in view of the maximum value of the evaluation value Wp.
                              F          p                =                  {                                                                                          (                                                                  x                        0                                            ,                                              y                        0                                                              )                                    |                                                                                                                                          (                                                          x                              -                                                              x                                0                                                                                      )                                                    2                                                +                                                                              (                                                          y                              -                                                              y                                0                                                                                      )                                                    2                                                                                      +                                                                                                                                                                                                                    (                                                      x                            -                            X                                                    )                                                2                                            +                                              y                        2                                                                              <                                      1                    /                    2                                                                                }                                    (                  Expression          ⁢                                          ⁢          11                )                                          W          p                =                              w            p                    -                                    ∑                                                q                  ≠                  p                                ∈                G                                      ⁢                                          w                q                            ⁢                                                                                          ∫                                              (                                                  x                          ,                          y                                                )                                                                                                                                  ⁢                                          ∈                                              ℬ                        ⁡                                                  [                          q                          ]                                                                                                      ,                                                            F                      p                                        ⁢                                                                                  ⁢                                          ξ                      ⁡                                              (                        x                        )                                                              ⁢                                          ⅆ                      x                                                                                                            ∫                                          x                      ∈                                              I                        q                                                                                                                                            ⁢                                                            ξ                      ⁡                                              (                        x                        )                                                              ⁢                                                                                  ⁢                                          ⅆ                      x                                                                                                                              (                  Expression          ⁢                                          ⁢          12                )            
The evaluation value Wp takes a smaller value when another boundary surface having a large value is located in the Fresnel zone of some quasi-wavefront. ξ(x) is a weight function. For example, for the sake of simplicity, ξ(x) is set to ξ(x)=1.
A true quasi-wavefront thus extracted is a set of time periods from transmission of transmitted pulses at respective measurement locations until reflected waves of the transmitted pulses which impinge on and are reflected from tangent planes of a surface of the target object O are directly received.
Next, in step S106, the shape measurement instrument obtains the shape of the object O from the true quasi-wavefronts extracted in step S105 using Expression (5).
Thus, in the SEABED method, the shape of the target object O can be directly estimated by the inverse transform expressed as Expression (5). Therefore, the shape of the object O can be considerably quickly measured.
In the SEABED method described above, a shape can be estimated by the inverse boundary scattering transform expressed as Expression (5) or (7). An image obtained by the inverse boundary scattering transform is not an approximate solution and is a mathematically exact solution, and can be directly obtained rather than based on iterative calculation. These advantages enable the SEABED method to be an imaging algorithm capable of calculation at higher resolution than those of conventional methods and at considerably high speed.
Patent Document 1: Japanese Laid-Open Patent Publication No. 2006-343205
Non-Patent Document 1: Takuya SAKAMOTO and Tom SATO, “A Nonparametric Target Shape Estimation Algorithm for UWB Pulse Radar Systems,” TECHNICAL REPORT OF IEICE, A•P2003-36, vol. 103, no. 120, pp. 1-6, Jun. 19, 2003
Non-Patent Document 2: Takuya SAKAMOTO and Tom SATO, “A Phase Compensation Algorithm for High-Resolution Shape Estimation Algorithms with Pulse Radars,” TECHNICAL REPORT OF IEICE, A•2004-72, vol. 104, no. 202, pp. 37-42, Jul. 22, 2004
Non-Patent Document 3: Takuya SAKAMOTO and Tom SATO, “A Target Shape Estimation Algorithm for Pulse Radar Systems based on Boundary Scattering Transform,” IEICE TRANSACTIONS on Communications, Vol. E87-B, No. 5, May 2004, pp. 1357-1365
Non-Patent Document 4: Shouhei KIDERA, Takuya SAKAMOTO and Toru SATO, “A Fast Imaging Algorithm with Bi-static Antenna for UWB Pulse Radar Systems,” 34-th Electromagnetic Theory Symposium of IEICE, EMT-05-58, November 2005
Non-Patent Document 5: Shouhei Kidera, Takuya Sakamoto and Toru Sato, “A High-resolution 3-D Imaging Algorithm with Linear Array Antennas for UWB Pulse Radar Systems,” IEEE AP-S International Symposium, USNC/URSI National Radio Science Meeting, AMEREM Meeting, pp. 1057-1060, July, 2006